#include<iostream>
using namespace std;
#define N 5
int maze[N][N] ={
    {0,1,0,0,0},
    {0,1,0,1,0},
    {0,0,0,0,0},
    {0,1,1,1,0},
    {0,0,0,1,0}
};

int directions[4][2] = {{-1,0}, {1,0},{0,-1}, {0,1}};

int visited[N][N] = {0};

void printPath(int path[N][N], int length){
    for (int i = 0; i < length; i++){
        for (int j = 0; j < length; j++) {
            cout << path[i][j] << "";
        }
        cout << endl;
    }
    cout << endl;
}

int dfs(int x, int y, int path[N][N]){
    if (x == N-1 && y == N - 1) {
        path[x][y] = 9;
        printPath(path, N);
        return 1;
    }

    visited[x][y] = 3;
    path[x][y] = 6;

    for (int i=0; i<4; i++) {
        int newX = x+ directions[i][0];
        int newY = y+directions[i][1];

        if (newX >= 0 && newX < N && newY >= 0 && newY < N && maze[newX][newY] == 0 && !visited[newX][newY]){
            if (dfs(newX, newY, path)){
                return 1;
            }
        }
    }
    path[x][y] = 0;
    return 0;
}

int main() {
    int path[N][N] = {0};

    if(!dfs(0,0,path)) {
        cout << "No path found" << endl;
    }
    return 0;
}